package algorithms.a03sortadvance;

import algorithms.a02sortbasic.InsertionSort;
import algorithms.a02sortbasic.ShellSort;
import algorithms.utis.AlgorithmsUtis;
import algorithms.utis.SortTestHelper;
import org.apache.commons.lang3.RandomUtils;

import java.util.Arrays;

/**
 * 快速排序
 * 适用于有大量重复键值的数组排序
 *
 * @author 王昊然
 * @create 2018-02-06 11:39
 **/
public class QuickSort {

    /**
     * @param arr
     * @date: 2018/2/6 16:10
     * @author: 王昊然
     */
    public static void sort(Comparable[] arr) {

        int n = arr.length;

        //partition(arr, 0, n-1);
        //partitionDoubleWay(arr, 0, n - 1);
        partition3Way(arr, 0, n - 1);
    }

    /**
     * @param arr
     * @param v   起始下标
     * @param r   最大下标
     * @date: 2018-02-06 下午 11:32
     * @author: 王昊然
     */
    private static void partition(Comparable[] arr, int v, int r) {

        if (v >= r) return;

        //如果是近乎有序的数组，每次取第一个作为v不平衡性大，效率低，取随机位置进行优化
        int random = RandomUtils.nextInt(v, r);
        AlgorithmsUtis.swap(arr, v, random);

        int j = v;
        for (int i = v + 1; i <= r; i++) {
            if (arr[v].compareTo(arr[i]) > 0) {
                AlgorithmsUtis.swap(arr, i, j + 1);
                j++;
            }
        }

        AlgorithmsUtis.swap(arr, j, v);

        partition(arr, v, j - 1);
        partition(arr, j + 1, r);
    }


    /**
     * 双路partition
     *
     * @param arr
     * @param v   起始下标
     * @param r   最大下标
     * @date: 2018-02-06 下午 11:32
     * @author: 王昊然
     */
    private static void partitionDoubleWay(Comparable[] arr, int v, int r) {

        if (v >= r) return;

        //如果是近乎有序的数组，每次取第一个作为v不平衡性大，效率低，取随机位置进行优化
        int random = RandomUtils.nextInt(v, r);
        AlgorithmsUtis.swap(arr, v, random);

        int i = v + 1;
        int j = r;

        /**
         * 自己实现的，虽然正确但是理解起来很复杂，还是用慕课老师的吧
         */
        /*while (i <= j) {
            while (i <= j && arr[i].compareTo(arr[v]) <= 0) {
                i++;
            }
            while (j >= i && arr[j].compareTo(arr[v]) >= 0) {
                j--;
            }

            if (i >= j) break;
            AlgorithmsUtis.swap(arr, i, j);
        }*/

        while (true) {
            // 注意这里的边界, arr[i].compareTo(v) < 0, 不能是arr[i].compareTo(v) <= 0
            // 思考一下为什么?
            while (i <= r && arr[i].compareTo(arr[v]) < 0)
                i++;

            // 注意这里的边界, arr[j].compareTo(v) > 0, 不能是arr[j].compareTo(v) >= 0
            // 思考一下为什么?
            while (j >= v + 1 && arr[j].compareTo(arr[v]) > 0)
                j--;

            // 对于上面的两个边界的设定, 有的同学在课程的问答区有很好的回答:)
            // 大家可以参考: http://coding.imooc.com/learn/questiondetail/4920.html

            if (i > j)
                break;

            AlgorithmsUtis.swap(arr, i, j);
            i++;
            j--;
        }

        AlgorithmsUtis.swap(arr, j, v);

        partitionDoubleWay(arr, v, j - 1);
        partitionDoubleWay(arr, j + 1, r);
    }



    /**
     * 三路partition
     * 更适用于重复性很强的数组
     *
     * @param arr
     * @param v   起始下标
     * @param r   最大下标
     * @date: 2018-02-06 下午 11:32
     * @author: 王昊然
     */
    private static void partition3Way(Comparable[] arr, int v, int r) {

        if (v >= r) return;

        //如果是近乎有序的数组，每次取第一个作为v不平衡性大，效率低，取随机位置进行优化
        int random = RandomUtils.nextInt(v, r);
        AlgorithmsUtis.swap(arr, v, random);

        int lt = v;//为什么放到v位置而不是v+1？ 因为lt的含义是小于arr[v]的下标，初始时并不知道arr[v+1]<arr[v],所以不能放到v位置
        int gt = r+1;//为什么放到r+1位置而不是r？道理同上
        int i = v+1;
        while(i < gt){
            if(arr[i].compareTo(arr[v]) == 0){
                i++;
            }
            else if(arr[i].compareTo(arr[v]) < 0){
                AlgorithmsUtis.swap(arr, i, lt+1);
                lt++;
                i++;
            }else if(arr[i].compareTo(arr[v]) > 0){
                AlgorithmsUtis.swap(arr, i, gt-1);
                gt--;
            }
        }

        AlgorithmsUtis.swap(arr, v, lt);

        partition3Way(arr, v, lt-1);
        partition3Way(arr, gt, r);
    }


    public static void main(String[] args) {
        int N = 8000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 10); //1排序数组数值范围小，插入排序优势明显
//        Integer[] arr = SortTestHelper.generateNearlyOrderedArray(N, 100);
//        Integer[] arr = new Integer[]{4, 8, 7, 6, 5, 4, 3, 2, 1, 5, 3, 0, 6};
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        Integer[] arr3 = Arrays.copyOf(arr, arr.length);
        Integer[] arr4 = Arrays.copyOf(arr, arr.length);
        Integer[] arr5 = Arrays.copyOf(arr, arr.length);

        System.out.print("忽略--------");
        SortTestHelper.testSort(InsertionSort.class, arr);
        SortTestHelper.testSort(ShellSort.class, arr);
        SortTestHelper.testSort(MergeSort.class, arr);
        SortTestHelper.testSort(QuickSort.class, arr);
        System.out.println("----------");

        SortTestHelper.testSort(InsertionSort.class, arr2);
        SortTestHelper.testSort(ShellSort.class, arr3);
        SortTestHelper.testSort(MergeSort.class, arr4);
        SortTestHelper.testSort(QuickSort.class, arr5);
    }

}
